(^-^)ゞ
嗨，我是wec，今天是DAY 26。

🔎 題目難度與描述

難度：MEDIUM

題目描述：

給定一個可包含重複數字的整數數組nums，返回這些數字的所有唯一全排列。

🔎 解題思路＆程式碼

1️⃣ 回溯法

第1步： 對nums進行排列並創建一個空的result列表來儲存唯一的全排列。
第2步： 定義回溯函數backtrack與四個參數：
nums：原始數組。
path：當前的排列。
result：結果列表。
used：布林數組，用來標記元素是否被使用。
第3步： 當path的長度等於nums的長度，將當前的排列加入結果。
第4步： 遍歷nums，對每個元素執行以下操作：
1.如果元素已被使用，就跳過。
2.如果當前元素和前一個元素相同，且前一個元素未被使用，則跳過（避免重複排列）。
3.標記當前元素為已使用，加入path，然後進入下一層回溯。
4.回溯時，撤回當前選擇，將元素標記為未使用。
第5步： 首次調用backtrack函數，從空的path開始。
程式碼：

def permute_unique(nums)
  result = []
  nums.sort!
  backtrack(nums, [], result, [false] * nums.length)
  result
end

def backtrack(nums, path, result, used)
  if path.length == nums.length
    result << path.dup  
    return
  end

  (0...nums.length).each do |i|
    next if used[i] 

    if i > 0 && nums[i] == nums[i - 1] && !used[i - 1]
      next
    end

    used[i] = true  
    path << nums[i]  
    backtrack(nums, path, result, used) 
    path.pop
    used[i] = false 
  end
end

🔎 總結

時間複雜度

回溯法： O(n!)，n代表組數長度。
➡️ 第一步有先將組數做排列，是為了後面能更清楚的做去重的動做，然後使用used清楚標記出元素是不是已經被使用，這樣就可以確保每個元素在一次排列中只出現一次拉(b’V`)!!

那麽，以上就是今天的內容！

相信IT人動腦時都要吃點東西，所以今天邊寫邊吃日本便利商店買的軟糖。
明天要說：Ruby精選刷題！Medium路跑D-19(>∀･)⌒☆